1. Field;
The invention disclosed and claimed herein generally pertains to a method and apparatus for computing information pertaining to nodes of a weighted directed graph, such as a large social network graph. More particularly, the invention pertains to efficient computation of egonets in graphs of these types.
2. Description of the Related Art
A weighted directed graph generally comprises a number of nodes, and further comprises weighted edges that each extends from one of the nodes to another node. A weighted directed graph such as a social network can have a very large number of nodes, which may be on the order of millions or even billions of nodes. Also, social networks can have very important roles in fields exemplified by but not limited to healthcare, financial activities and crime prevention. It is therefore desirable to have tools available for processing graphs of these types with a high level of efficiency, in order to access and use important information contained in such graphs.
A weighted directed graph as described above comprises a number of neighboring subgraphs, which are referred to as egonets. Computing respective egonets of a large social network can be a very important activity, such as to find or discover anomalies. However, currently used solutions typically compute the egonets one at a time. These approaches tend to be very tedious and time-consuming, particularly when used for large graphs as referred to above.